//键盘输入一组非零整数，最后输入0为结束的标志，建立一颗二叉排序树，要求以二叉链表存储结构存储
#include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
    int data;
    struct Node *lchild,*rchild;
}Node,*Tree;

int insertNode(Node *root,int data);
int preOrderPrintTree(Node *root);
void freeTree(Node *root);
int insertNode1(Node **root,int data);


int main(){
    printf("please input data:\n");
    // Node root;
    // root.data=-1;
    Node *root=NULL;
    while (1)
       {
        // printf("data:%d\n",i);
        int data;
        scanf("%d",&data);
        if(data==0){
            break;
        }
        // insertNode(&root,data);
        insertNode1(&root,data);

    }
    // preOrderPrintTree(&root);
        preOrderPrintTree(root);

    // freeTree(root.lchild);
    // freeTree(root.rchild);
    return 0;
}

Node* creatNode(int data){
    Node* node = (Node*)malloc(sizeof(Node));
    node->data=data;
    node->lchild=NULL;
    node->rchild=NULL;
    return node;
}

int insertNode(Node *root,int data){
    if(root->data==-1){
        root->data=data;
        root->lchild=NULL;
        root->rchild=NULL;
        return 0;
    }
    if(root->data>=data){
        if(root->lchild==NULL){
            root->lchild=creatNode(data);
            return 0;
        }
        insertNode(root->lchild,data);
    }else{
        if(root->rchild==NULL){
            root->rchild=creatNode(data);
            return 0;
        }
        insertNode(root->rchild,data);
    }
    return 0;

}

int insertNode1(Node **root,int data){
    if(*root==NULL){
        *root=creatNode(data);
        return 0;
    }
    if((*root)->data>=data){
        // if(root->lchild==NULL){
        //     root->lchild=creatNode(data);
        //     return 0;
        // }
        insertNode1(&((*root)->lchild),data);
    }else{
        // if(root->rchild==NULL){
        //     root->rchild=creatNode(data);
        //     return 0;
        // }
        insertNode1(&((*root)->rchild),data);
    }
    return 0;

}
int preOrderPrintTree(Node *root){
    if(root==NULL){
        return 0;
    }
    printf("%d ",root->data);
    preOrderPrintTree(root->lchild);
    preOrderPrintTree(root->rchild);
    return 0;
}

// 释放二叉树内存
void freeTree(Node *root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->lchild);
    freeTree(root->rchild);
    free(root);
}


